/*
 * @lc app=leetcode.cn id=164 lang=typescript
 *
 * [164] 最大间距
 */

// @lc code=start
function maximumGap(nums: number[]): number {
  // 将数组元素先低位排序，再高位排序
  const base = 2 ** 16;
  const count = new Array(base).fill(0);
  const temp = new Array(nums.length);

  // 低16位排序
  for (let num of nums) {
    count[num & 0xffff] += 1;
  }
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  for (let i = nums.length - 1; i >= 0; i--) {
    let num = nums[i];
    temp[--count[num & 0xffff]] = num;
  }

  // 重置count
  count.fill(0);

  // 高16位排序
  for (let num of nums) {
    count[(num & 0xffff0000) >> 16] += 1;
  }
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  for (let i = nums.length - 1; i >= 0; i--) {
    let num = temp[i];
    nums[--count[(num & 0xffff0000) >> 16]] = num;
  }

  // 计算结果
  let result = 0;
  for (let i = 1; i < nums.length; i++) {
    result = Math.max(result, nums[i] - nums[i - 1]);
  }
  return result;
}
// @lc code=end
